#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    // LCR 166. 珠宝的最高价值
    // https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size();
        int n = frame[0].size();
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        for (int i = 1; i<=m; ++i)
        {
            for (int j = 1; j<=n; ++j)
            {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i-1][j-1];
            }
        }

        return dp[m][n];
    }

    // 931. 下降路径最小和
    // https://leetcode.cn/problems/minimum-falling-path-sum/
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> dp(n+1, vector<int>(n+2, INT_MAX));

        for (int j = 0; j <= n; ++j)
            dp[0][j] = 0;
        
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]}) + matrix[i-1][j-1];
            }
        }

        return *min_element(dp[n].begin(), dp[n].end());
    }

    // 64. 最小路径和
    // https://leetcode.cn/problems/minimum-path-sum/
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MAX));
        dp[0][1] = 0, dp[1][0] = 0;

        for (int i = 1; i<=m; ++i)
        {
            for (int j = 1; j<=n; ++j)
            {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
            }
        }

        return dp[m][n];
    }
};